home *** CD-ROM | disk | FTP | other *** search
/ Computer Shopper 242 / Issue 242 - April 2008 - DPCS0408DVD.ISO / Software Money Savers / VirtualDub / Source / VirtualDub-1.7.7-src.7z / src / h / vd2 / system / list.h < prev    next >
Encoding:
C/C++ Source or Header  |  2006-03-14  |  6.1 KB  |  276 lines
  1. //    VirtualDub - Video processing and capture application
  2. //    System library component
  3. //    Copyright (C) 1998-2004 Avery Lee, All Rights Reserved.
  4. //
  5. //    Beginning with 1.6.0, the VirtualDub system library is licensed
  6. //    differently than the remainder of VirtualDub.  This particular file is
  7. //    thus licensed as follows (the "zlib" license):
  8. //
  9. //    This software is provided 'as-is', without any express or implied
  10. //    warranty.  In no event will the authors be held liable for any
  11. //    damages arising from the use of this software.
  12. //
  13. //    Permission is granted to anyone to use this software for any purpose,
  14. //    including commercial applications, and to alter it and redistribute it
  15. //    freely, subject to the following restrictions:
  16. //
  17. //    1.    The origin of this software must not be misrepresented; you must
  18. //        not claim that you wrote the original software. If you use this
  19. //        software in a product, an acknowledgment in the product
  20. //        documentation would be appreciated but is not required.
  21. //    2.    Altered source versions must be plainly marked as such, and must
  22. //        not be misrepresented as being the original software.
  23. //    3.    This notice may not be removed or altered from any source
  24. //        distribution.
  25.  
  26. #ifndef f_LIST_H
  27. #define f_LIST_H
  28.  
  29. class ListNode {
  30. public:
  31.     ListNode *next, *prev;
  32.  
  33.     void Remove() {
  34.         next->prev = prev;
  35.         prev->next = next;
  36. #ifdef _DEBUG
  37.         prev = next = 0;
  38. #endif
  39.     }
  40.  
  41.     void InsertAfter(ListNode *node) {
  42.         next = node;
  43.         prev = node->prev;
  44.         if (node->prev) node->prev->next = this;
  45.         node->prev = this;
  46.     }
  47.  
  48.     void InsertBefore(ListNode *node) {
  49.         next = node->next;
  50.         prev = node;
  51.         if (node->next) node->next->prev = this;
  52.         node->next = this;
  53.     }
  54.  
  55.     ListNode *NextFromHead() const {
  56.         return prev;
  57.     }
  58.  
  59.     ListNode *NextFromTail() const {
  60.         return next;
  61.     }
  62. };
  63.  
  64. class List {
  65. private:
  66. public:
  67.     ListNode head, tail;
  68.  
  69.     // <--- next             prev --->
  70.     //
  71.     // head <-> node <-> node <-> tail
  72.  
  73.     List();
  74.     List(int) {}
  75.  
  76.     void Init();
  77.  
  78.     void AddHead(ListNode *node) {
  79.         node->InsertAfter(&head);
  80.     }
  81.  
  82.     void AddTail(ListNode *node) {
  83.         node->InsertBefore(&tail);
  84.     }
  85.  
  86.     ListNode *RemoveHead();
  87.     ListNode *RemoveTail();
  88.  
  89.     bool IsEmpty() const {
  90.         return !head.prev->prev;
  91.     }
  92.  
  93.     ListNode *AtHead() const {
  94.         return head.prev;
  95.     }
  96.  
  97.     ListNode *AtTail() const {
  98.         return tail.next;
  99.     }
  100.  
  101.     void Take(List& from);
  102.     void Swap(List& with);
  103. };
  104.  
  105. // Templated classes... templated classes good.
  106.  
  107. template<class T> class List2;
  108.  
  109. template<class T>
  110. class ListNode2 : public ListNode {
  111. friend List2<T>;
  112. public:
  113.     void InsertBefore(ListNode2<T> *node) { ListNode::InsertBefore(node); }
  114.     void InsertAfter(ListNode2<T> *node) { ListNode::InsertAfter(node); }
  115.  
  116.     void Remove() { ListNode::Remove(); }
  117.     T *NextFromHead() const { return static_cast<T *>(static_cast<ListNode2<T>*>(ListNode::NextFromHead())); }
  118.     T *NextFromTail() const { return static_cast<T *>(static_cast<ListNode2<T>*>(ListNode::NextFromTail())); }
  119. };
  120.  
  121. template<class T>
  122. class List2 : public List {
  123. public:
  124.     List2<T>() {}
  125.  
  126.     // This is a really lame, stupid way to postpone initialization of the
  127.     // list.
  128.  
  129.     List2<T>(int v) : List(v) {}
  130.  
  131.     void AddHead(ListNode2<T> *node) { List::AddHead(node); }
  132.     void AddTail(ListNode2<T> *node) { List::AddTail(node); }
  133.     T *RemoveHead()   { return static_cast<T *>(static_cast<ListNode2<T>*>(List::RemoveHead())); }
  134.     T *RemoveTail()   { return static_cast<T *>(static_cast<ListNode2<T>*>(List::RemoveTail())); }
  135.     T *AtHead() const { return static_cast<T *>(static_cast<ListNode2<T>*>(List::AtHead())); }
  136.     T *AtTail() const { return static_cast<T *>(static_cast<ListNode2<T>*>(List::AtTail())); }
  137.  
  138.     // I must admit to being pampered by STL (end is different though!!)
  139.  
  140.     T *begin() const { return AtHead(); }
  141.     T *end() const { return AtTail(); }
  142.  
  143.     void take(List2<T>& from) { List::take(from); }
  144.  
  145.     class iterator {
  146.     protected:
  147.         ListNode2<T> *node;
  148.         ListNode2<T> *next;
  149.  
  150.     public:
  151.         iterator() {}
  152.         iterator(const iterator& src) throw() : node(src.node), next(src.next) {}
  153.  
  154.         bool operator!() const throw() { return 0 == next; }
  155.         T *operator->() const throw() { return (T *)node; }
  156.         operator bool() const throw() { return 0 != next; }
  157.         operator T *() const throw() { return (T *)node; }
  158.         T& operator *() const throw() { return *(T *)node; }
  159.     };
  160.  
  161.     // fwit: forward iterator (SAFE if node disappears)
  162.     // rvit: reverse iterator (SAFE if node disappears)
  163.  
  164.     class fwit : public iterator {
  165.     public:
  166.         fwit() throw() {}
  167.         fwit(const fwit& src) throw() : iterator(src) {}
  168.         fwit(ListNode2<T> *start) throw() {
  169.             node = start;
  170.             next = start->NextFromHead();
  171.         }
  172.  
  173.         const fwit& operator=(ListNode2<T> *start) throw() {
  174.             node = start;
  175.             next = start->NextFromHead();
  176.  
  177.             return *this;
  178.         }
  179.  
  180.         fwit& operator++() throw() {
  181.             node = next;
  182.             next = node->NextFromHead();
  183.  
  184.             return *this;
  185.         }
  186.  
  187.         const fwit& operator+=(int v) throw() {
  188.             while(next && v--) {
  189.                 node = next;
  190.                 next = node->NextFromHead();
  191.             }
  192.  
  193.             return *this;
  194.         }
  195.  
  196.         fwit operator+(int v) const throw() {
  197.             fwit t(*this);
  198.  
  199.             t += v;
  200.  
  201.             return t;
  202.         }
  203.  
  204.         // This one's for my sanity.
  205.  
  206.         void operator++(int) throw() {
  207.             ++*this;
  208.         }
  209.     };
  210.  
  211.     class rvit : public iterator {
  212.     public:
  213.         rvit() throw() {}
  214.  
  215.         rvit(ListNode2<T> *start) throw() {
  216.             node = start;
  217.             next = start->NextFromTail();
  218.         }
  219.  
  220.         const rvit& operator=(ListNode2<T> *start) throw() {
  221.             node = start;
  222.             next = start->NextFromTail();
  223.  
  224.             return *this;
  225.         }
  226.  
  227.         rvit& operator--() throw() {
  228.             node = next;
  229.             next = node->NextFromTail();
  230.  
  231.             return *this;
  232.         }
  233.  
  234.         const rvit& operator-=(int v) throw() {
  235.             while(next && v--) {
  236.                 node = next;
  237.                 next = node->NextFromTail();
  238.             }
  239.  
  240.             return *this;
  241.         }
  242.  
  243.         rvit operator-(int v) const throw() {
  244.             rvit t(*this);
  245.  
  246.             t -= v;
  247.  
  248.             return t;
  249.         }
  250.  
  251.         // This one's for my sanity.
  252.  
  253.         void operator--(int) throw() {
  254.             --*this;
  255.         }
  256.     };
  257. };
  258.  
  259. template<class T>
  260. class ListAlloc : public List2<T> {
  261. public:
  262.     ListAlloc<T>() {}
  263.     ~ListAlloc<T>() {
  264.         dispose();
  265.     }
  266.  
  267.     void dispose() {
  268.         T *node;
  269.  
  270.         while(node = RemoveHead())
  271.             delete node;
  272.     }
  273. };
  274.  
  275. #endif
  276.